// Problem:    187
// Title:      Semiprimes
// Date:       22-Mar-2008
// Difficulty: 1
// Fun Rating: 1
// Time:       n ln ln n
// Space:      n
// Closed:     Y
// Answer:     17427258

#include <iostream>
#include "prime.h"

void solve_problem_187()
{
#if 0
	const int N = 30;
#else
	const int N = 100000000;
#endif

	int count = 0;

#if 1
	std::vector<int> primes;
	find_primes_below((N+1)/2, primes);

	int k = (int)primes.size();
	for (int i=0, j=k-1; i<k; i++)
	{
		int p = primes[i];
		while (p*primes[j] >= N)
			j--;
		if (j < i)
			break;
		count += (j-i+1);
	}
#else
	prime_numbers primes((N-1)/2);
	//std::copy(primes.crbegin(), primes.crend(), std::ostream_iterator<int>(std::cout, "\n"));
	//std::cout << "Size: " << primes.size() << std::endl;
	//return;

	int k = (int)primes.size();
	prime_numbers::const_reverse_iterator rit = primes.crbegin();
	prime_numbers::const_iterator it = primes.cbegin();
	for (int i = 0, j = k - 1; it != primes.cend(); ++it, ++i)
	{
		for (int p = *it; p*(*rit) >= N; ++rit, --j);
		if (*rit < *it)
			break;
		count += (j-i+1);
	}
#endif

	std::cout << count << std::endl;
}
